package com.qding.park.common.utils.sort;

import java.util.Arrays;
import java.util.Stack;

/**
 * @ClassName QuickSort
 * @Description TODO(快速排序)
 * @author Administrator
 * @Date 2016年8月27日 下午11:33:21
 * @version 1.0.0
 */
public class QuickSort {

	public static void main(String[] args) {
		int[] ints = { 12, 14312, 312, 31, 3214, 324, 324, 32, 4, 324, 32 };
		quickSort(ints);
		System.out.println(Arrays.toString(ints));

		int[] intqs = { 12, 14312, 312, 31, 3214, 324, 324, 32, 4, 324, 32 };
		quickSort(intqs, 0, intqs.length - 1);
		System.out.println(Arrays.toString(intqs));
	}

	/**
	 * @Description ( 快速排序_跌代版)
	 * @param arr
	 *            快速排序_跌代版
	 */
	public static void quickSort(int[] arr) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(0);
		stack.push(arr.length - 1);
		while (stack.empty() == false) {
			int end = stack.pop(), start = stack.pop();
			if (start >= end)
				continue;
			int part = arr[start];
			int locate = start;
			int pre = start, post = end;
			while (pre < post) {
				while (pre < post && arr[post] > part)
					post--;
				if (pre > post)
					break;
				arr[locate] = arr[post];
				locate = post;
				while (pre < post && arr[pre] <= part)
					pre++;
				if (pre > post)
					break;
				arr[locate] = arr[pre];
				locate = pre;
			}
			arr[locate] = part;
			stack.push(start);
			stack.push(locate - 1);
			stack.push(locate + 1);
			stack.push(end);
		}
	}

	/**
	 * @Description (快速排序_递归版)
	 * @param arr
	 * @param start
	 * @param end
	 * @return
	 */
	public static int partition(int[] arr, int start, int end) {
		int part = arr[start];
		int locate = start;
		while (start < end) {
			while (end > start && arr[end] > part)
				end--;
			if (end <= start) {
				break;
			}
			arr[locate] = arr[end];
			locate = end;
			while (start < end && arr[start] <= part)
				start++;
			if (start >= end) {
				break;
			}
			arr[locate] = arr[start];
			locate = start;
		}
		arr[locate] = part;
		return locate;
	}

	public static void quickSort(int[] arr, int start, int end) {
		if (start >= end)
			return;
		int mid = partition(arr, start, end);
		quickSort(arr, start, mid - 1);
		quickSort(arr, mid + 1, end);
	}
}
